// 2025/3/20
// https://leetcode.cn/problems/palindrome-partitioning/description/?envType=study-plan-v2&envId=top-100-liked
// 分割回文串

class Solution {
    public:
        vector<vector<string>> ans;
        vector<string> tmp;
    
        bool isPast(string& s, int left, int right)
        {
            while (left < right && s[left] == s[right])
            {
                left++;
                right--;
            };
            if (left >= right) return true;
            else return false;
        }
    
        void dfs(string& s, int pos)
        {
            if (pos == s.size())
            {
                ans.push_back(tmp);
                return;
            }
    
            int n = s.size();
            for (int i = pos; i < n; i++)
            {
                if (s[pos] == s[i] && isPast(s, pos, i))
                {
                    tmp.push_back(string(s.begin() + pos, s.begin() + i + 1));
                    dfs(s, i + 1);
                    tmp.pop_back();
                }
            }
        }
    
        vector<vector<string>> partition(string s) {
            dfs(s, 0);
            return ans;
        }
    };